import 'dart:core';
import 'dart:math';
import 'dart:ui' as ui;

import 'package:flutter/cupertino.dart';
import 'package:flutter/material.dart';

///四叉树学习
///https://blog.csdn.net/u013052238/article/details/118889232
///https://davidhsu666.com/archives/quadtree_in_2d/
///https://blog.csdn.net/MaxLykoS/article/details/108910953?utm_medium=distribute.pc_relevant.none-task-blog-baidujs_title-0&spm=1001.2101.3001.4242
///
class QuadtreeLearningWidget extends StatefulWidget {
  @override
  _QuadtreeLearningWidgetState createState() => _QuadtreeLearningWidgetState();
}

class _QuadtreeLearningWidgetState extends State<QuadtreeLearningWidget>
    with SingleTickerProviderStateMixin {
  Quadtree quadtree =
      Quadtree(0, -1, Rect.fromLTRB(0, 0, 800, 800), <Offset>[], <Quadtree>[]);

  List<Flink> links = <Flink>[];
  List<FNode> nodes = <FNode>[];

  @override
  void initState() {
    super.initState();
    initializeNodes();
  }

  void initializeNodes() {
    var initialRadius = 100;
    var initialAngle = 0.8;
    // var initialAngle = pi*(3-sqrt(5));

    print("initialAngle:$initialAngle");
    print("sqrt(5):${sqrt(5)}");
    print("pi:${pi}");
    print(" cos(10):${cos(10)}");

    List<Offset> initOffset = <Offset>[];
    List<double> listX = <double>[];
    List<double> listY = <double>[];

    //偏移
    double transplant = 400;
    for (int i = 0; i < 15; i++) {
      var radius = (initialRadius * sqrt(i));
      var angle = i * initialAngle;
      var offset = Offset(transplant * 2 + radius * cos(angle),
          transplant + radius * sin(angle));
      listX.add(offset.dx);
      listY.add(offset.dy);
      print("初始化:${offset.toString()}");
      initOffset.add(offset);

      nodes.add(FNode(offset, offset,i));
    }

    double xMin = listX.reduce(min);
    double xMax = listX.reduce(max);

    double yMin = listY.reduce(min);
    double yMax = listY.reduce(max);

    print("xMin:$xMin---xMax$xMax---yMin:$yMin---yMax$yMax");

    //xMin-1，这些防止点在线上，rect.contains 没算进去
    quadtree = Quadtree(
        0,
        -1,
        Rect.fromLTRB(xMin - 1, yMin - 1, xMax + 1, yMax + 1),
        <Offset>[],
        <Quadtree>[]);

    for (Offset offset in initOffset) {
      quadtree.insert(quadtree, offset);
    }
    quadtree.insert(quadtree, Offset(100, 100));
    tick();

    for (Offset offset in quadtree.queryRectPoint(
        quadtree, Rect.fromLTRB(400, 339.6, 800, 500))) {
      print("查询区域点${offset.toString()}");
    }
  }

  double alpha = 0.2;
  double gravity = 0.2;
  double width = 80;
  double height = 80;
  double strength = 0.7;
  double distance = 150;
  double friction = 0.8;
  var _time = 0;

  /**
   * 一次计算
   */
  void tick() {
    _time++;
    if ((alpha *= 0.99) < 0.005) {
      // Log.e("Force", "time="+_time);
      return;
    }

    //随机模拟牵连关系
    for (int pointIndex = 0; pointIndex < nodes.length; pointIndex++) {
      int value = Random().nextInt(nodes.length);
      links.add(Flink(FlinkNode(nodes[pointIndex].point, pointIndex + 1),
          FlinkNode(nodes[value].point, pointIndex + 1)));
    }

    if (nodes == null || links == null) {
      return;
    }



    final int nodeCount = nodes.length;
    int linkCount = links.length;

    //拉力计算方法
    for (int i = 0; i < linkCount; i++) {
      Flink link = links[i];
      FlinkNode sourceLinkNode = link.source;
      FlinkNode targetLinkNode = link.target;

      Offset sourceNode = sourceLinkNode.point;
      Offset targetNode = targetLinkNode.point;
      double dx = targetNode.dx - sourceNode.dx;
      double dy = targetNode.dy - sourceNode.dy;
      double d = dx * dx + dy * dy;
      if (d > 0) {
        d = sqrt(d);

        d = alpha * linkStrength() * (d - linkDistance(link)) / d;
        dx *= d;
        dy *= d;

        double k = sourceLinkNode.weight * 1.0 / (targetLinkNode.weight + sourceLinkNode.weight);
        targetNode.translate( -dx * k, - dy * k);

        k = 1 - k;
        sourceNode.translate( dx * k, dy * k);

      }
    }
    //
    // //聚力计算方法，让整个分布趋于椭圆
    // double k = alpha * gravity;
    // double k2 =  alpha * (gravity + 0.05);
    // if (k != 0) {
    //   double w = width / 2;
    //   double h = height / 2;
    //   for (int i = 0; i < nodeCount; i++) {
    //     Offset node = nodes[i].point;
    //     node.translate((w - node.dx) * k, (h - node.dy) * k2);
    //
    //   }
    // }
    //
    // //排斥力计算，使用四叉树让减少计算，提高效率
    // if (charge != 0) {
    //   final QuadTree quadTree = getQuadTree(nodes);
    //   forceAccumulate(quadTree.root);
    //   for (int i = 0; i < nodeCount; i++) {
    //     final FNode node = nodes.get(i);
    //     if (!node.isStable()) {
    //       visitQuadTree(quadTree.root, node, minX, minY, maxX, maxY);
    //     }
    //   }
    // }
    //
    // for (int i = 0; i < nodeCount; i++) {
    //   FNode node = nodes[i];
    //   if (false) {
    //     node.point.translate(-node.point.dx+node.lastPoint.dx, -node.point.dy+node.lastPoint.dy);
    //   } else {
    //     node.point.translate(-(node.lastPoint.dx - (node.lastPoint.dx = node.point.dx)) * friction, -(node.dy - (node.dy = node.dy)) * friction);
    //
    //   }
    // }
  }

  void tick2() {
    _time++;
    if ((alpha *= 0.99) < 0.005) {
      // Log.e("Force", "time="+_time);
      return;
    }

    //随机模拟牵连关系
    for (int pointIndex = 0; pointIndex < nodes.length; pointIndex++) {
      int value = Random().nextInt(nodes.length);
      links.add(Flink(FlinkNode(nodes[pointIndex].point, pointIndex + 1),
          FlinkNode(nodes[value].point, pointIndex + 1)));
    }

    if (nodes == null || links == null) {
      return;
    }



    final int nodeCount = nodes.length;
    int linkCount = links.length;

    //拉力计算方法
    for (int i = 0; i < linkCount; i++) {
      Flink link = links[i];
      FlinkNode sourceLinkNode = link.source;
      FlinkNode targetLinkNode = link.target;

      Offset sourceNode = sourceLinkNode.point;
      Offset targetNode = targetLinkNode.point;
      double dx = targetNode.dx - sourceNode.dx;
      double dy = targetNode.dy - sourceNode.dy;
      double d = dx * dx + dy * dy;

      Rect rect = Rect.fromPoints(sourceNode, targetNode);
      List<Offset> rectPoints =  quadtree.queryRectPoint(quadtree, rect);
      if(rectPoints.length>2){
        for(Offset rectPoint in rectPoints){
          if(rectPoint != sourceLinkNode && rectPoint != targetLinkNode){

            var rectPoint1 = rectPoint;
            rectPoint = targetNode;
          }
        }
      }
    }
    //
    // //聚力计算方法，让整个分布趋于椭圆
    // double k = alpha * gravity;
    // double k2 =  alpha * (gravity + 0.05);
    // if (k != 0) {
    //   double w = width / 2;
    //   double h = height / 2;
    //   for (int i = 0; i < nodeCount; i++) {
    //     Offset node = nodes[i].point;
    //     node.translate((w - node.dx) * k, (h - node.dy) * k2);
    //
    //   }
    // }
    //
    // //排斥力计算，使用四叉树让减少计算，提高效率
    // if (charge != 0) {
    //   final QuadTree quadTree = getQuadTree(nodes);
    //   forceAccumulate(quadTree.root);
    //   for (int i = 0; i < nodeCount; i++) {
    //     final FNode node = nodes.get(i);
    //     if (!node.isStable()) {
    //       visitQuadTree(quadTree.root, node, minX, minY, maxX, maxY);
    //     }
    //   }
    // }
    //
    // for (int i = 0; i < nodeCount; i++) {
    //   FNode node = nodes[i];
    //   if (false) {
    //     node.point.translate(-node.point.dx+node.lastPoint.dx, -node.point.dy+node.lastPoint.dy);
    //   } else {
    //     node.point.translate(-(node.lastPoint.dx - (node.lastPoint.dx = node.point.dx)) * friction, -(node.dy - (node.dy = node.dy)) * friction);
    //
    //   }
    // }
  }

  linkStrength() {
    double k = 1;
    return strength * k;
  }

  double linkDistance(Flink link) {
    return distance + 20 + 20;
  }

  @override
  Widget build(BuildContext context) {
    return Material(
      child: Center(
          child: Container(
        child: Listener(
          onPointerDown: (details) {
            // var offset =
            //     Offset(details.localPosition.dx, details.localPosition.dy);
            // quadtree.insert(quadtree, offset);
            // print("点击：${offset.toString()}");
            // setState(() {});
          },
          child: Container(
            width: double.infinity,
            height: double.infinity,
            color: Color(0xffffffff),
            child: RepaintBoundary(
              //隔离重绘控件，singlescrollview 滑动发生重绘，导致画笔paint响应
              child: CustomPaint(
                painter: _CirclePainter(quadtree: quadtree, links: links),
              ),
            ),
          ),
        ),
      )),
    );
  }

  @override
  void dispose() {
    super.dispose();
  }
}

class _CirclePainter extends CustomPainter {
  Quadtree quadtree;
  List<Flink> links;

  _CirclePainter({required this.quadtree, required this.links});

  double radius = 20;

  @override
  void paint(Canvas canvas, Size size) {
    Paint _painter = Paint()
      ..color = Color(0xFF00FDF4)
      ..style = PaintingStyle.fill
      ..isAntiAlias = true;

    Paint _painterLine = Paint()
      ..color = Color(0xFFF50000)
      ..style = PaintingStyle.stroke
      ..isAntiAlias = true;

    Paint _painterTowLine = Paint()
      ..color = Color(0xFF000000)
      ..style = PaintingStyle.stroke
      ..isAntiAlias = true;

    // if(quadtree.nodes != null && quadtree.nodes.length==0){
    //   drawPath(quadtree, canvas, _painterLine);
    // }else{
    //   for (Quadtree quadtreeChild in quadtree.nodes) {
    //     drawPath(quadtreeChild, canvas, _painterLine);
    //   }
    // }
    var quadtreeList = quadtree.queryPathPoint(quadtree);

    //点十字架的象限域划分
    for (int i = 0; i < quadtreeList.length; i++) {
      var child = quadtreeList[i];
      if (child.currentLevel == 1) {
        _painterLine..color = Color(0xFFECC817);
      } else if (child.currentLevel == 2) {
        _painterLine..color = Color(0xFF68F103);
      } else if (child.currentLevel == 3) {
        _painterLine..color = Color(0xFF00E5DB);
      } else if (child.currentLevel == 4) {
        _painterLine..color = Color(0xFF0712F8);
      }
      drawPath(quadtreeList[i], canvas, _painterLine);
    }

    //每个点
    drawPoint(quadtree, canvas, _painter);

    //两点连线
    drawTwoPointPath(canvas, _painterTowLine);
  }

  // void drawPoint(Quadtree quadtree, ui.Canvas canvas, ui.Paint _painter) {
  //   for(Offset point in quadtree.queryPoint(quadtree)){
  //     print("drawPoint：${point.toString()}");
  //     canvas.drawCircle(
  //         point, 4, _painter);
  //   }
  //
  // }
  void drawPoint(Quadtree quadtree, ui.Canvas canvas, ui.Paint _painter) {
    for (PointColor pointColor in quadtree.queryPoint(quadtree)) {
      _painter.color = pointColor.color;
      for (Offset point in pointColor.offset) {
        // print("drawPoint：${point.toString()}");
        canvas.drawCircle(point, radius, _painter);
      }
    }
  }

  void drawPath(Quadtree quadtree, ui.Canvas canvas, ui.Paint _painterLine) {
    if (quadtree.rectangle != null &&
        quadtree.nodes != null &&
        quadtree.nodes.length == 4) {
      var path = Path();

      print("${quadtree.rectangle.left}---${quadtree.point.dy}");
      print("${quadtree.rectangle.right}---${quadtree.point.dy}");

      var startX = quadtree.rectangle.left;
      var startY = quadtree.point.dy;
      var endX = quadtree.rectangle.right;
      var endY = quadtree.point.dy;

      path.moveTo(startX, startY);
      path.lineTo(endX, endY);
      path.moveTo(quadtree.point.dx, quadtree.rectangle.top);
      path.lineTo(quadtree.point.dx, quadtree.rectangle.bottom);
      canvas.drawPath(path, _painterLine);
    }
  }

  void drawTwoPointPath(ui.Canvas canvas, ui.Paint _painterLine) {
    for (var link in links) {
      var p00 = link.source.point;
      var p03 = link.target.point;

      double distanceX = 0;
      double distanceY = 0;

      //取两圆x，y长度
      distanceY = (p03.dy - p00.dy).abs();
      distanceX = (p03.dx - p00.dx).abs();

      double twoPointDistance =
          sqrt(distanceY * distanceY + distanceX * distanceX);
      //目标点
      double endX = 0;
      double endY = 0;

      //按等比例缩放移动x，y点
      endX = p03.dx - (p03.dx - p00.dx) * radius / twoPointDistance;
      endY = p03.dy - (p03.dy - p00.dy) * radius / twoPointDistance;

      double centerX = (p00.dx + endX) / 2;
      double centerY = (p00.dy + endY) / 2;

      double lenX = (endX - p00.dx);
      double lenY = (endY - p00.dy);
      double lenXY = sqrt((lenX * lenX + lenY * lenY));

      print("object:radian lenXY 角度--:${acos(lenX / lenXY)}---");

      //得出弧度，lenX / lenXY 为出发点圆夹角
      double radian = acos(lenX / lenXY) * (p00.dy < p03.dy ? 1 : -1);

      //得出，半圆为Π，得出补角弧度，pi / 2-radian
      double centerRadian = pi / 2 - radian;
      double tempAssX = (centerX + lenXY / 4 * cos(centerRadian));
      double tempAssY = (centerY - lenXY / 4 * sin(centerRadian));

      //计算两边的箭头点，比例是试出来的
      double arrowAssX = (centerX + lenXY * cos(centerRadian));
      double arrowAssY = (centerY - lenXY * sin(centerRadian));
      double arrowAssX2 = (centerX - lenXY / 3 * cos(centerRadian));
      double arrowAssY2 = (centerY + lenXY / 3 * sin(centerRadian));

      var path = Path();
      path.moveTo(p00.dx, p00.dy);

      path.quadraticBezierTo(tempAssX, tempAssY, endX, endY);
      // path.lineTo(endX,endY);
      canvas.drawPath(path, _painterLine);

      //画箭头,
      drawArrow(canvas, centerX, centerY, arrowAssX, arrowAssY, endX, endY,
          arrowAssX2, arrowAssY2);

      //中心点
      Paint _painterLine1 = Paint()
        ..color = Color(0xFFFFFFFF)
        ..style = PaintingStyle.fill
        ..isAntiAlias = true;
      canvas.drawCircle(Offset(centerX, centerY), 2, _painterLine1);

      //控制心点
      Paint _painterLine2 = Paint()
        ..color = Color(0xFFFFA100)
        ..style = PaintingStyle.fill
        ..isAntiAlias = true;
      canvas.drawCircle(Offset(tempAssX, tempAssY), 2, _painterLine2);
    }
  }

  void drawArrow(
    Canvas canvas,
    double centerX,
    double centerY,
    double controlX,
    double controlY,
    double endX,
    double endY,
    double controlX2,
    double controlY2,
  ) {
    Paint _painterArrow = Paint()
      ..color = Color(0xFFF50000)
      ..style = PaintingStyle.stroke
      ..isAntiAlias = true;
    var pathArrow = Path();

    double controlEndDistance = sqrt((endX - controlX) * (endX - controlX) +
        (endY - controlY) * (endY - controlY));

    //进行比例缩放得出箭头点
    double lineToX = endX - (endX - controlX) * 10 / controlEndDistance;
    double lineToY = endY - (endY - controlY) * 10 / controlEndDistance;

    double lineToX2 = endX - (endX - controlX2) * 18 / controlEndDistance;
    double lineToY2 = endY - (endY - controlY2) * 18 / controlEndDistance;

    pathArrow.moveTo(endX, endY);
    pathArrow.lineTo(lineToX, lineToY);
    pathArrow.moveTo(endX, endY);
    pathArrow.lineTo(lineToX2, lineToY2);
    canvas.drawPath(pathArrow, _painterArrow);
  }

  @override
  bool shouldRepaint(covariant CustomPainter oldDelegate) {
    return true;
  }
}

class Quadtree {
  int MAX_OBJECTS = 4;
  int MAX_LEVELS = 3;

  //当前等级
  int currentLevel;

  //当前父等级
  int currentPLevel;

  //区域
  Rect rectangle;

  List<Rect> childRects = <Rect>[];

  //该区域容器的物体集合
  List<Offset> objects;

  //中节点位置
  Offset point = Offset(-1, -1);

  //当前象限下 只能有4个
  List<Quadtree> nodes;

  late Quadtree quadtree;

  Quadtree(this.currentLevel, this.currentPLevel, this.rectangle, this.objects,
      this.nodes) {
    point = Offset(rectangle.left + (rectangle.right - rectangle.left) / 2,
        rectangle.top + (rectangle.bottom - rectangle.top) / 2);
    // for (int index = 0; index < 4; index++) {
    //   if (index == 0) {
    //     childRects.add(
    //         Rect.fromLTRB(quadtree.rectangle.left, quadtree.rectangle.top,
    //             quadtree.point.dx, quadtree.point.dy));
    //   }
    //   if (index == 1) {
    //     childRects.add(Rect.fromLTRB(quadtree.point.dx, quadtree.rectangle.top,
    //         quadtree.rectangle.right, quadtree.point.dy));
    //   }
    //
    //   if (index == 2) {
    //     childRects.add(Rect.fromLTRB(quadtree.point.dx, quadtree.point.dy,
    //         quadtree.rectangle.right, quadtree.rectangle.bottom));
    //   }
    //   if (index == 3) {
    //     childRects.add(Rect.fromLTRB(quadtree.rectangle.left, quadtree.point.dy,
    //         quadtree.point.dx, quadtree.rectangle.bottom));
    //   }
    // }
  }

  void init() {
    quadtree = Quadtree(
        0, -1, Rect.fromLTRB(0, 0, 800, 800), <Offset>[], <Quadtree>[]);
  }

  void insert(Quadtree quadtree, Offset point) {
    if (!quadtree.rectangle.contains(point)) {
      return;
    }

    if (quadtree.currentLevel > MAX_LEVELS) {
      return;
    }

    if (quadtree.objects.length < MAX_OBJECTS) {
      quadtree.objects.add(point);
      return;
    }

    if (quadtree.nodes != null && quadtree.nodes.length == 0) {
      spitRect(quadtree, point);
    } else {
      for (Quadtree quadtreeChild in quadtree.nodes) {
        quadtreeChild.insert(quadtreeChild, point);
      }
    }
  }

  void spitRect(Quadtree quadtree, Offset point) {
    for (int index = 0; index < 4; index++) {
      if (index == 0) {
        Quadtree quadChild = Quadtree(
            quadtree.currentLevel + 1,
            quadtree.currentPLevel + 1,
            Rect.fromLTRB(quadtree.rectangle.left, quadtree.rectangle.top,
                quadtree.point.dx, quadtree.point.dy),
            <Offset>[],
            <Quadtree>[]);
        quadtree.nodes.add(quadChild);
      }
      if (index == 1) {
        Quadtree quadChild = Quadtree(
            quadtree.currentLevel + 1,
            quadtree.currentPLevel + 1,
            Rect.fromLTRB(quadtree.point.dx, quadtree.rectangle.top,
                quadtree.rectangle.right, quadtree.point.dy),
            <Offset>[],
            <Quadtree>[]);
        quadtree.nodes.add(quadChild);
      }

      if (index == 2) {
        Quadtree quadChild = Quadtree(
            quadtree.currentLevel + 1,
            quadtree.currentPLevel + 1,
            Rect.fromLTRB(quadtree.point.dx, quadtree.point.dy,
                quadtree.rectangle.right, quadtree.rectangle.bottom),
            <Offset>[],
            <Quadtree>[]);
        quadtree.nodes.add(quadChild);
      }

      if (index == 3) {
        Quadtree quadChild = Quadtree(
            quadtree.currentLevel + 1,
            quadtree.currentPLevel + 1,
            Rect.fromLTRB(quadtree.rectangle.left, quadtree.point.dy,
                quadtree.point.dx, quadtree.rectangle.bottom),
            <Offset>[],
            <Quadtree>[]);
        quadtree.nodes.add(quadChild);
      }
      //继续插入
      insert(quadtree.nodes[index], point);
    }
  }

  ///查询所有的点
  List<Offset> queryAllPoint(Quadtree quadtree) {
    List<Offset> points = <Offset>[];
    points.addAll(quadtree.objects);
    if (quadtree.nodes != null) {
      for (Quadtree child in quadtree.nodes) {
        points.addAll(queryAllPoint(child));
      }
    }
    return points;
  }

  ///为不同等级的象限点添加颜色区分
  List<PointColor> queryPoint(Quadtree quadtree) {
    List<PointColor> points = <PointColor>[];
    Color color = Color(0xFFEF0606);
    if (quadtree.currentLevel == 1) {
      color = Color(0xFFECC817);
    } else if (quadtree.currentLevel == 2) {
      color = Color(0xFF68F103);
    } else if (quadtree.currentLevel == 3) {
      color = Color(0xFF00E5DB);
    } else if (quadtree.currentLevel == 4) {
      color = Color(0xFF0712F8);
    }
    points.add(new PointColor(quadtree.objects, color));

    if (quadtree.nodes != null) {
      for (Quadtree child in quadtree.nodes) {
        points.addAll(queryPoint(child));
      }
    }
    return points;
  }

  List<Quadtree> queryPathPoint(Quadtree quadtree) {
    List<Quadtree> quadtrees = <Quadtree>[];
    quadtrees.add(quadtree);
    if (quadtree.nodes != null) {
      for (Quadtree child in quadtree.nodes) {
        quadtrees.addAll(queryPathPoint(child));
      }
    }
    return quadtrees;
  }

  ///查询区域中的所有点
  List<Offset> queryRectPoint(Quadtree quadtree, Rect rect) {
    List<Offset> pointRect = <Offset>[];
    Rect intersect = rect.intersect(quadtree.rectangle);
    if (intersect.right - intersect.left < 0 ||
        intersect.bottom - intersect.top < 0) {
      return pointRect;
    } else {
      //查询树中该区域的的所有点是否在在区域中
      for (Offset point in quadtree.objects) {
        if (rect.contains(point)) {
          pointRect.add(point);
        }
      }
      for (Quadtree child in quadtree.nodes) {
        pointRect.addAll(queryRectPoint(child, rect));
      }
    }
    return pointRect;
  }
}

class PointColor {
  List<Offset> offset;
  Color color;

  PointColor(this.offset, this.color);
}

class Flink {
  FlinkNode source;
  FlinkNode target;

  Flink(this.source, this.target);
}

class FlinkNode {
  Offset point;
  double weight;

  FlinkNode(this.point, this.weight);
}

class FNode {
  Offset point;
  Offset lastPoint;
  int nodeIndex;

  FNode(this.point, this.lastPoint, this.nodeIndex);
}
